package lk;

import java.util.LinkedList;
import java.util.List;

public class D230916 {
    // 反转字符串中的单词
    // 遍历字符串, 遇到空格跳过, 不是空格就将一个单词 头插 进链表
    // 最后拼接起来
    public String reverseWords(String s) {
        char[] str = s.toCharArray();
        List<String> list = new LinkedList<>();
        for (int i = 0; i < str.length; i++) {
            if (str[i] == ' ') {
                continue;
            } else {
                StringBuilder tmp = new StringBuilder();
                while (i < str.length && str[i] != ' ') {
                    tmp.append(str[i++]);
                }
                list.add(0, tmp.toString());
            }
        }
        return String.join(" ", list);
    }


    // 除自身以外数组的乘积
    // 这题主要难点是 数组中 有 0 的情况
    // 如果没有 0, 可以计算出整个数组的乘积, 然后除于自身, 就是除自身以外数组的乘积

    // 1. 左右乘积列表
    // 遍历两次数组, 分别计算 i 的左边乘积 和 右边乘积, 使用两个数组存储
    // 两个乘积相乘, 就是除自身以外数组的乘积
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        // L 和 R 分别表示左右两侧的乘积列表
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];
        // L[i] 为索引 i 左侧所有元素的乘积
        // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }
        // R[i] 为索引 i 右侧所有元素的乘积
        // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }
        // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }


    // 2. 优化了第一种方案, 空间复杂度为 O(1)
    public int[] productExceptSelf2(int[] nums) {
        int[] ret = new int[nums.length];

        // 先计算左边的乘积
        ret[0] = 1; // 第一个元素左侧没有元素, 左边乘积为 1
        for (int i = 1; i < nums.length; i++) {
            ret[i] = nums[i - 1] * ret[i - 1];
        }

        // 计算右边乘积
        int right = 1; // 从右往前遍历数组, right 代表右侧元素的乘积
        for (int i = nums.length - 1; i >= 0; i--) {
            ret[i] *= right;
            right *= nums[i];
        }
        return ret;
    }


    // 递增的三元子序列
    // 1. 暴力枚举, 三重循环, 超时

    // 2. 双向遍历, 存储 nums[i] 左边的最小元素, 和 右边的最大元素
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        // 存放 nums[i] 左边的最小元素
        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }
        // 存放 nums[i] 右边的最大元素
        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }

        // 遍历数组, 根据 leftMin 和 rightMax, 看 nums[i] 是否是中间元素
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }
        return false;
    }


    // 贪心
    public boolean increasingTriplet2(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }
}
